package DataStructure.graph;

import DataStructure.linear.Stack;

public class DepthFirstPaths {
    //索引代表顶点，值代表当前顶点是否被搜索
    private boolean[] marked;
    //起点
    private int s;
    //索引代表顶点，值代表当前顶点路径上最后一个顶点
    private int[] edgeTo;

    //构造函数，找出G图中起点为s的所有路径
    public DepthFirstPaths(Graph G,int s){
        this.marked=new boolean[G.V()];
        this.s=s;
        this.edgeTo=new int[G.V()];
        dfs(G,s);
    }

    //使用深度优先搜索找出G图中v顶点的所有相邻顶点
    private void dfs(Graph G,int v){
        //把v标识为已搜索
        marked[v]=true;
        //遍历v的邻接表拿到每一个相邻的顶点继续递归搜索
        for (Integer w : G.adj(v)) {
            //如果w没有被搜索则递归
            if(!marked[w]){
                //到达顶点w的的路径上最后一个顶点是v
                edgeTo[w]=v;
                dfs(G,w);
            }
        }

    }

    //判断w顶点与s顶点是否存在路径
    public boolean hasPathTo(int v){
        return marked[v];
    }

    //找出从起点s到顶点v的路径（就是该路径经过的顶点）
    public Stack<Integer> pathTo(int v){
        if(!hasPathTo(v)){
            return null;
        }
        //创建栈对象保存路径中的所有顶点
        Stack<Integer> path = new Stack<>();
        //通过循环从顶点v开始一直往前找到起点为止
        for (int x = v; x !=s ; x=edgeTo[x]) {
            path.push(x);
        }
        //把起点放入栈中
        path.push(s);
        return path;
    }
}
